//
// Created by hitfy on 2018/4/22.
//
#include <bits/stdc++.h>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;//包含cv命名空间

vector<pair<int, int>> nodes;
vector<pair<int, int>> originNodes;

const int nodeSize = 5000;

void createRandomNodes(){
    set<pair<int, int>> nodeset;
    int times = 0;
    while(nodeset.size() < nodeSize){
        nodeset.insert(pair<int, int>(rand() % 100, rand() % 100));
        times++;
    }
    nodes.clear();
    originNodes.clear();
    copy(nodeset.begin(), nodeset.end(), back_inserter(nodes));
    copy(nodeset.begin(), nodeset.end(), back_inserter(originNodes));
    printf("The times of generating random points:%d\n", times);
}

void printNodes(vector<pair<int, int>> &nodes){
    printf("nodes number:\t%ld\n", nodes.size());
    vector<pair<int, int>>::iterator it = nodes.begin();
    while(it != nodes.end()){
        printf("(%d, %d), ", it->first, it->second);
        it++;
    }
    printf("\n");
}

void convexHull_Graham_Scan(){
    //求出Y坐标最小的p0
    int YMin = INT_MAX, point0;
    for(int i = 0; i < nodes.size(); i++){
        if(nodes[i].second < YMin){
            YMin = nodes[i].second;
            point0 = i;
        }
    }
    //按照与p0的极角排序
    set<pair<float, int>> polarset;//每个点与point0的极角的tan值和在原nodes集合中的位置
    for(int i = 0; i < nodes.size(); i++){
        if(i == point0)
            continue;
        int x = nodes[i].first - nodes[point0].first, y = nodes[i].second - nodes[point0].second;
        polarset.insert(pair<float, int>((float)y / x, i));
    }
    //此时polarset的排序为负无穷到0再到正无穷，要调整为0到正无穷接着负无穷到0
//    printf("nodes number:\t%ld\n", polarset.size());
    set<pair<float, int>>::iterator tempit = polarset.begin();
    vector<pair<float, int>> polarvector;
    while(tempit != polarset.end()){
        if(tempit->first < 0)
            polarvector.push_back(*tempit);
        else
            break;
        tempit++;
    }
    polarvector.insert(polarvector.begin(), tempit, polarset.end());
//    for(int i = 0; i < polarvector.size(); i++)
//        printf("(%f, %d(%d, %d)), ", polarvector[i].first, polarvector[i].second,
//               nodes[polarvector[i].second].first, nodes[polarvector[i].second].second);
//    printf("\n");
    //将point0,point1,point2压入栈
    if(polarset.size() < 3)
        return;
    stack<int> pointstack;
    vector<pair<float, int>>::iterator it = polarvector.begin();
    pointstack.push(point0);
    pointstack.push(it->second);
    int sectop = it->second;
    it++;
    pointstack.push(it->second);
    int top = it->second;
    it++;
    while(it != polarvector.end()){
        int next = it->second;
        while((nodes[sectop].first - nodes[next].first)
              * (nodes[top].second - nodes[next].second)
              - (nodes[sectop].second - nodes[next].second)
                * (nodes[top].first - nodes[next].first) < 0) {
            pointstack.pop();
            top = pointstack.top();
            pointstack.pop();
            sectop = pointstack.top();
            pointstack.push(top);
            printf("polar:%f, nodesindex:%d, top:%d, sectop%d, next:%d)\n ",
                   it->first, it->second, top, sectop, next);
        }
        pointstack.push(next);
        sectop = top;
        top = pointstack.top();
        it++;
    }
    nodes.clear();
    while(!pointstack.empty()) {
        nodes.push_back(originNodes[pointstack.top()]);
        pointstack.pop();
    }
}

int main() {
    clock_t startTime,endTime;
    createRandomNodes();
    startTime = clock();
    convexHull_Graham_Scan();
    endTime = clock();
    printf("%ld\t%ld\t%ld\n", startTime, endTime, CLOCKS_PER_SEC);
    printf("Algorithm run time:\t%lfms\n", (double)(endTime - startTime) / CLOCKS_PER_SEC * 1000);
    printNodes(originNodes);
    printNodes(nodes);

    int w = 600;
    int pw = w / 100;
    Mat image( w, w, CV_8UC3, Scalar(255,255,255));
    //绘制网格
//    for(int i = 0; i < w/6; i++) {
//        line(image, Point(pw * i, 0), Point(pw*i, w), Scalar( 0, 0, 0 ));
//        line(image, Point(0, pw*i), Point(w, pw*i), Scalar( 0, 0, 0 ));
//    }
    for(int i = 0; i < originNodes.size(); i++)//绘制所有原始点并标为绿色
        circle( image, Point( originNodes[i].first * pw, originNodes[i].second * pw), 3, Scalar( 0, 255, 0 ), -1, 8);
    for(int i = 0; i < nodes.size(); i++)//绘制凸包点并标为红色
        circle( image, Point( nodes[i].first * pw, nodes[i].second * pw), 3, Scalar( 0, 0, 255 ), -1, 8);
    imshow( "ConvexHull_Graham_Scan", image);
    waitKey();
    return 0;
}